package com.leetcode.leetcode2;

import java.util.ArrayList;
import java.util.List;

/**
 *  括号生成
 * @author: luhd
 * @create: 2021-09-02
 */
public class Practice22 {
    public static void main(String[] args) {
        List<String> str = generateParenthesis(3);
        System.out.println(str);
        //Iterator<String> iterator = str.stream().iterator();
        //while(iterator.hasNext()) {
        //    System.out.println(iterator.next());
        //}
        str.stream().spliterator().forEachRemaining(System.out::println);
    }
    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        dfs(n,n,"",res);
        return res;
    }
    // 深度优先遍历搜索，返回所有可能的情况(回溯和递归)
    public static void dfs(int left,int right,String curStr,List<String> res){
        //List<String> res = new ArrayList<>();

        if(left==0 && right==0){    // 递归终止的条件
            res.add(curStr);
            return;
        }
        if(left>0){     // 如果左括号还有就可以继续拼接做括号
            dfs(left-1,right,curStr+"(",res);
        }
        if(right>left){     // 如果右括号数大于左括号数就可以拼接右括号
            dfs(left,right-1,curStr+")",res);
        }
    }
}
